package com.tgy.algorithm.base._图_01;

import java.util.*;

public class _dijkstra算法 {


    public static HashMap<Node<Integer>,Integer> dijkstra(Node<Integer> startNode){

        HashMap<Node<Integer>, Integer> retMap = new HashMap<>();
        // 自己的节点，先创建
        retMap.put(startNode, 0);
        HashSet<Node<Integer>> visitSet = new HashSet<>();
        while (true) {
            Node<Integer> node = findMinPath(retMap,visitSet);
            if (node == null) break;
            visitSet.add(node);
            Integer distance = retMap.get(node);
            for (Edge<Integer> edge : node.edges) {
                Node<Integer> toNode = edge.to;
                if (!visitSet.contains(toNode)) {
                    Integer distanceNext = retMap.get(toNode);
                    if (distanceNext == null) {
                        retMap.put(toNode,distance + edge.value);
                    }else {
                        retMap.put(toNode,Math.min(distance + edge.value,distanceNext));
                    }
                }
            }
        }


        return retMap;
    }

    // 这里获取最小值，可以使用小根堆
    public static Node<Integer> findMinPath(Map<Node<Integer>,Integer> paths, HashSet<Node<Integer>> visitSet){

        int minDistance = Integer.MAX_VALUE;
        Node<Integer> minNode = null;
        for (Map.Entry<Node<Integer>, Integer> nodeIntegerEntry : paths.entrySet()) {
            Node<Integer> node = nodeIntegerEntry.getKey();
            Integer distance = nodeIntegerEntry.getValue();
            if (!visitSet.contains(node) && distance < minDistance) {
                minDistance = distance;
                minNode = node;
            }
        }

        return minNode;
    }

    public static void main(String[] args) {
        int[][] datas = new int[][]{
                {0,1,1},
                {0,2,7},
                {0,3,6},
                {1,4,170},
                {1,2,2},
                {2,4,23},
                {2,3,2},
                {3,4,4},
        };

        Graph<Integer> graph = _拓扑排序.createGraph(datas);
        HashMap<Node<Integer>, Integer> hashMap = dijkstra(graph.nodes.get(0));
        System.out.println(hashMap);
    }
}
